Skip to main content

Count of Range Sum

Question​

Given an array nums of integers, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

How many range sums lie in the inclusive range [lower, upper]?

Example 1
None

Solution​

all//Count of Range Sum.py


def countRangeSum(nums, lower, upper):
    res = 0
    prefix_sum = [0]
    for num in nums:
        prefix_sum.append(prefix_sum[-1] + num)
    # sort the prefix_sum array
    sorted_prefix_sum = sorted(prefix_sum)
    # use two pointer to scan the sorted_prefix_sum array
    j = 0
    for i in range(len(sorted_prefix_sum)):
        while j < len(sorted_prefix_sum) and sorted_prefix_sum[j] - sorted_prefix_sum[i] < lower:
            j += 1
        k = j
        while k < len(sorted_prefix_sum) and sorted_prefix_sum[k] - sorted_prefix_sum[i] <= upper:
            k += 1
        res += k - j
    return res